package lc20240617;
/**
  * @description 求最大子数组和
  * @author 不知名帅哥
  * @date 2024/6/17 9:15
  * @version 1.0
*/
public class MaxChildArraySum {
    public static void main(String[] args) {
int[] nums={-2,1,-3,4,-1,2,1,-5,4};
        int res = maxSubArray(nums);
        System.out.println(res);
    }
    public static int maxSubArray(int[] nums) {
        int maxNum = nums[0];
        int length = nums.length;
        if (length == 1) {

            return maxNum;
        }

        //初始化dp：dp[i]表示前i个元素最大的连续子数组和
        int[] dp=new int[length];
        dp[0]=nums[0];
        for (int i = 1; i < length; i++) {
            if (dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }else {
                dp[i]=nums[i];
            }
            maxNum=Math.max(dp[i],maxNum);
        }
        return maxNum;
    }
}
